/*
2021-8-8
https://leetcode-cn.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
*/
class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int>res;
        int a[100010],n=0;
        int g[100010];
        int len=0;
        g[0]=2e9;
        int ans=0;
        for(auto t:obstacles)
        {
            a[n++]=t;
            int l=0,r=len;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(a[n-1]>=g[mid]) l=mid;
                else r=mid-1;
            }
            len=max(len,r+1);
            g[r+1]=a[n-1];
            ans=r+1;
            res.push_back(ans);
        }
        return res;
    }
};
